package src.leetcode.dp.medium_1049;

import java.util.*;

public class lastStoneWeightII {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lastStoneWeightII(new int[]{31,26,33,21,40}));
    }
}

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }

        int target = sum / 2;
        boolean dp[] = new boolean[target + 1];
        dp[0] = true;
        for (int stone : stones) {
            for(int j = target; j >= stone; j--) {
                dp[j] = dp[j] || dp[j - stone];
            }
        }

        for (int i = target; i >= 0; i--) {
            if(dp[i]) return 2 * (target - i) + sum % 2;
        }
        return target;
    }
}
